#ifndef UUID_65EBB0896FCB42FEE689CD99810C3BD5
#define UUID_65EBB0896FCB42FEE689CD99810C3BD5

#include <vector>
#include <ctime>
#include <cassert>
#include "common.hpp"

//#include <gvl/math/cmwc.hpp>



#define LOPREC 1

#define ZEROFIRST 0

#define BIJECTIVE 1

struct Coder1
{
	Coder1(ByteWriter writer)
	: low(0)
	, range(0xffffffff)
	, help(0)
	, buffer(0)
	, skip(true)
	, writer(writer)
#if BIJECTIVE
	, prevend(0)
#endif
	{
	}
	
	uint64 low;
	uint32 range;
	uint32 help, buffer;
	bool skip;

#if BIJECTIVE
	uint64 prevend; // Bit pattern of previous end
#endif
	
	//std::vector<unsigned char> buf;
	ByteWriter writer;
	
	void reset()
	{
		low = 0;
		range = 0xffffffff;
		help = 0;
		buffer = 0;
		skip = true;
#if BIJECTIVE
		prevend = 0;
#endif
		//buf.clear();
	}
	
	void encode(int y, int p)
	{
#if LOPREC
		uint32 r = (range >> 12) * p;
#else
		uint32 r = uint32((uint64(range) * p) >> 12);
#endif

#if ZEROFIRST
		uint32 mask = -y;
#else
		uint32 mask = y - 1;
#endif

		low += r & mask;
		range = (range & mask) + (r ^ mask) - mask;

		//printf("%x, %x, r = (%x >> 12) * %x == %x\n", range, low, range, p, r);
		
		while (range < (1<<24))
		{
			range = (range << 8); // + 0xff;
			shift();
		}
		
		//printf("%x, %x, r = (%x >> 12) * %x == %x\n", range, low, range, p, r);

		print_debug();
	}

	void encode_uni(int y)
	{
		// !ZEROFIRST
		
		low += (range >>= 1) & (y - 1);

		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}
	}

	void encode_unibits(int y, int bits)
	{
		// !ZEROFIRST

		low += (range >>= bits) * y;

		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}
	}

	void encode_shift(uint32 base, uint32 size, int sh)
	{
		assert(size > 0 && base <= uint32(1<<sh) && (uint32(1<<sh) - base >= size));

		uint32 r = range >> sh;

		assert(r > 0);

		low += r * base;
		range = r * size;

		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}
	}

	void encode_range(uint32 base, uint32 size, uint32 total)
	{
		assert(size > 0 && base + size <= total);

		uint32 r = (range / total);

		assert(r > 0);

		low += r * base;
		range = r * size;

		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}
	}

	void encode_tiny0()
	{
		--range;
		assert(range > 0);
		/*
		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}
		*/
	}

	void encode_huge1()
	{
		uint32 r = range - 1;
		assert(r > 0);

		low += r;
		range = 1;

		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}
	}

	void encode_tiny1()
	{
		++low;
		--range;
		assert(range > 0);

		/*
		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}*/
	}

	void encode_huge0()
	{
		range = 1;

		while (range < (1<<24))
		{
			range = (range << 8);
			shift();
		}
	}

	void bit_align()
	{
		// Discard some of the range so that it becomes a power of two
		uint32 r = 1;
		while((r << 1) <= range)
			r <<= 1;

		range = r;
	}

	static uint64 computeEnd(uint64 low, uint32 range, uint64 prev);

	void dontFlush()
	{
#if BIJECTIVE
		prevend = computeEnd(low, range, prevend);
#endif
	}

	void shift();
	
	void flush()
	{
#if BIJECTIVE
		uint64 tmp = computeEnd(low, range, prevend);

		uint32 c = uint32(tmp >> 32);
		writer.put(buffer + c);
		--c;
		for (; help > 0; help--)
			writer.put(c);

		while(tmp & 0xffffffff)
		{
			writer.put(uint8(tmp >> 24));
			tmp <<= 8;
		}
#elif 1
		// ((low + range - 1) & ~0xffffff) will be in the range
		uint32 tmp = uint32((low + range - 1) >> 24);

		unsigned int c = tmp >> 8;
		writer.put(buffer + c);
		--c;
		for (; help > 0; help--)
			writer.put(c);
		writer.put(tmp);
#else
		for(int i = 0; i < 5; ++i)
			shift();
#endif

		writer.flush();
	}

#if 0
	void flush_huge1()
	{
		uint32 r = range - 1;
		assert(r > 0);

		low += r;
		range = 1;

		uint32 tmp = uint32((low >> 24)) + 1;

		unsigned int c = tmp >> 8;
		writer.put(buffer + c);
		--c;
		for (; help > 0; help--)
			writer.put(c);
		writer.put(tmp);

		writer.flush();
	}
#endif

	void print_debug()
	{
		//printf("range = %x\n", range);
	}
};



struct Decoder1
{
	Decoder1(ByteReader reader)
	: range(0xffffffff), reader(reader)
	{
		init();
	}
	
	uint32 buffer, range;

	ByteReader reader;
	
	void init()
	{
		range = 0xffffffff;
		for (int i = 0; i < 4; i++)
			buffer = (buffer << 8) + reader.get();
	}
	
	int decode(int p)
	{
#if LOPREC
		uint32 r = (range >> 12) * p;
#else
		uint32 r = uint32((uint64(range) * p) >> 12);
#endif

#if ZEROFIRST
		int y = buffer >= r;
		uint32 mask = 0 - y;
#else
		int y = buffer < r;
		uint32 mask = y - 1;
#endif

		buffer -= r & mask;
		range = (range & mask) + (r ^ mask) - mask;
		
		while (range < (1<<24))
		{
			range = (range << 8);
			buffer = (buffer << 8) + reader.get();
		}

		print_debug();
		
		return y;
	}

	int decode_uni()
	{
		// (1) buffer < range [note: this only holds if the encoder cannot write 0xff as byte 1-4 in the stream, which it can't]
		// (2) range < 0x100000000
		// (3) (range >> 1) < 0x80000000 [from 2]
		// (4) (buffer - (range >> 1)) <= (range >> 1) [from 1]
		// (5) (buffer - (range >> 1)) < 0x80000000 [from 3, 4]
		// (6) (buffer - (range >> 1)) > -0x80000000 [from 3]
		// [5, 6] means the sign bit of (buffer - (range >> 1)) is the result of (buffer < (range >> 1))

		// !ZEROFIRST

		uint32 y = (buffer - (range >>= 1)) >> 31;

		buffer -= range & (y - 1);
		
		while (range < (1<<24))
		{
			range = (range << 8);
			buffer = (buffer << 8) + reader.get();
		}
		
		return y;
	}

	int decode_unibits(int bits)
	{
		// !ZEROFIRST

		range >>= bits;

		int y = 0;

		// The division or loop version should really be selected depending on bit count
	#if 0
		for(int i = bits - 1; i >= 0; --i)
		{
			uint32 r = range << i;
			uint32 mask = ((buffer - r) >> 31) - 1;
			y = (y << 1) - mask;
			buffer -= r & mask;
		}
	#else
		y = (buffer / range) & ((1 << bits) - 1); // buffer may be >= (range << bits) in invalid streams
		buffer -= range * y;
	#endif
		
		while (range < (1<<24))
		{
			range = (range << 8);
			buffer = (buffer << 8) + reader.get();
		}

		return y;
	}

	uint32 get_count(uint32 total)
	{
		return buffer / (range /= total);
	}

	uint32 get_count_shift(int sh)
	{
		return buffer / (range >>= sh);
	}

	void decoded_range(uint32 base, uint32 size)
	{
		buffer -= range * base;
		range *= size;

		while (range < (1<<24))
		{
			range = (range << 8);
			buffer = (buffer << 8) + reader.get();
		}

		print_debug();
	}

	int decode_tiny1_huge0()
	{
		if(buffer)
		{
			--buffer;
			--range;
			return 1;
		}
		else
		{
			range = 1;
			
			while (range < (1<<24))
			{
				range = (range << 8);
				buffer = (buffer << 8) + reader.get();
			}

			return 0;
		}
	}

	void print_debug()
	{
		//printf("range = %x\n", range);
	}
};

struct Coder3
{
	static uint32 const TOP = (1<<24);
	static uint32 const BOT = (1<<15);

	Coder3(ByteWriter writer)
	: low(0)
	, range(0xffffffff)
	, writer(writer)
#if BIJECTIVE
	, prevend(0)
#endif
	{
	}
	
	uint32 low;
	uint32 range;
	ByteWriter writer;

#if BIJECTIVE
	uint32 prevend;
#endif

	static uint32 shiftPrevEnd3(uint32 low, uint32 prev);
	static uint32 computeEnd3(uint32 low, uint32 range, uint32 prev);

	void renorm()
	{
		if((low ^ (low+range)) >= TOP && range < BOT)
		{
			low = low;
		}

		while ((low ^ (low+range)) < TOP || range < BOT &&
            ((range = (0-low) & (BOT-1)),1))
		{
#if BIJECTIVE
			prevend = shiftPrevEnd3(low, prevend);
#endif
			writer.put(low >> 24);
			range <<= 8;
			low <<= 8;
		}
	}

	void encode(int y, int p)
	{
		uint32 r = (range >> 12) * p;
		uint32 mask = y - 1;

		low += r & mask;
		range = (range & mask) + (r ^ mask) - mask;

		renorm(); //RENORM();
	}

	void encode_range(uint32 base, uint32 size, uint32 total)
	{
		assert(size > 0 && base + size <= total);

		uint32 r = (range / total);

		assert(r > 0);

		low += r * base;
		range = r * size;

		renorm(); //RENORM();
	}

	void encode_shift(uint32 base, uint32 size, int sh)
	{
		uint32 r = (range >> sh);

		assert(r > 0);

		low += r * base;
		range = r * size;

		renorm(); //RENORM();
	}

	void dontFlush()
	{
#if BIJECTIVE
		prevend = computeEnd3(low, range, prevend);
#endif
	}

	void flush()
	{
	#if BIJECTIVE
		uint32 end = computeEnd3(low, range, prevend);

		while(end)
		{
			writer.put(end >> 24);
			end <<= 8;
		}
	#else
		for(int i = 0; i < 4; ++i)
		{
			writer.put(low >> 24);
			low <<= 8;
		}
	#endif
		writer.flush();
	}
};


struct Decoder3
{
	static uint32 const TOP = (1<<24);
	static uint32 const BOT = (1<<15);

	Decoder3(ByteReader readerInit)
	: low(0)
	, code(0)
	, range(0xffffffff)
	, reader(readerInit)
#if BIJECTIVE
	, prevend(0)
#endif
	{
		for(int i = 0; i < 4; ++i)
		{
			code = (code << 8) + reader.get();
		}
	}

	uint32 low, code;
	uint32 range;

#if BIJECTIVE
	uint32 prevend;
#endif

	ByteReader reader;

	void renorm()
	{
		while ((low ^ (low+range)) < TOP || range < BOT &&
			((range = (0-low) & (BOT-1)),1))
		{
#if BIJECTIVE
			prevend = Coder3::shiftPrevEnd3(low, prevend);
#endif
			code = (code << 8) | reader.get();
			range <<= 8;
			low <<= 8;
		}
	}

#if BIJECTIVE
	bool mayEnd()
	{
		prevend = Coder3::computeEnd3(low, range, prevend);
		if(reader.empty() && code == prevend)
			return true;
		return false;
	}
#endif

	int decode(int p)
	{
		uint32 r = (range >> 12) * p;

		int y = (code - low) < r;
		uint32 mask = y - 1;

		low += r & mask;
		range = (range & mask) + (r ^ mask) - mask;
		
		renorm(); // RENORM();
		
		return y;
	}

	uint32 get_count(uint32 total)
	{
		return (code - low) / (range /= total);
	}

	uint32 get_count_shift(int sh)
	{
		return (code - low) / (range >>= sh);
	}

	void decoded_range(uint32 base, uint32 size)
	{
		low += range * base;
		range *= size;

		renorm(); // RENORM();
	}
};

/*
struct BitModel
{
	BitModel()
	{
	}

	uint32 prob;

	uint32 p()
	{ return prob; }

	void update(int y)
	{
		uint32 mask = 0 - y;
      
		int shift = 4;
      
		int correction1 = (1<<(shift)) - 2;
      
		prob += int32(1 + ((4095 + correction1) & mask) - prob) >> shift;
	}

};*/

#endif // UUID_65EBB0896FCB42FEE689CD99810C3BD5
